Traditional digital processors (processor) are complex logic devices that execute user instructions in a sequential fashion to produce a desired result for the user. Referring to FIG. 1, these instructions are stored in a Memory 101, and are read from Memory 101 and executed by the processor. Instructions differ from other instructions by the sequence of bits inside the instruction. Each bit can assume one of two states, providing two possible outcomes. One state is arbitrarily called a ‘zero’ state, often represented by the number ‘0’, and the other state is called a ‘one’ state, often represented by the number ‘1’. Other nomenclature may be used to describe these two states, including but not limited to terms such as ‘on’ and ‘off’, ‘set’ and ‘clear’, or ‘high’ and ‘low’. There are also technologies that can encode three or more states into a single bit of information, however, at present the state of the art in electronics needed to implement three or more states in a bit is of sufficient complexity and size that it takes fewer transistors to implement two bits of two states each (which can provide up to four possible states between the two bits) than it does to implement a single bit with three or four states. Regardless of whether the bits in an instruction represent two states each, or more than two states each, each instruction is defined by the state of each bit and the order with which the bits are placed in the instruction.
One of the more novel features processors can provide for society is the ability to electronically control the flow of large quantities of data through a communications network called the World Wide Web or the Internet. The Internet today has become so intertwined with society that, for example, it is now used to do searches for information that used to take people hours, days, or even longer to perform by hand. The Internet is also used to process the transfer of funds and other banking services, engage in on-line shopping, send and receive pictures, books or papers, pre-recorded or live video, music, and sound, and control much of society's utility infrastructure.
Sadly, there are people who seek to malevolently take control of processors connected to the Internet to disrupt commerce, engage in acts of theft, vandalism, sabotage, or revenge, inconvenience people or disrupt their lives, or even endanger people and damage society's infrastructure by changing the sequence of instructions inside a processor's Main Memory 101a. The new sequences maliciously placed in processors' Main Memory 101a can instruct equipment that controls society's utilities to engage in damaging behavior, violate safety protocols (and thus endanger people or the environment), compromise personal, privileged, or classified information, shut down utilities, improperly move funds around, or by taking over a sufficient number of processors, instruct them to simultaneously send service requests to overwhelm other processors and shut them down. If the disruption is to processors controlling society's infrastructure and the disruption is successful at shutting down something such as electrical power, if not restored soon chaos could result, plunging society into anarchy.
To mitigate the hostile takeover of processors, a series of protective responses have been developed. These responses include firewalls, which are specialized processors designed to recognize invalid attempts to pass Internet traffic from the unprotected Internet to a protected localized network, and block such traffic.
Another product is a Gateway, which changes, or translates, the Internet addresses of processors inside a protected local network before the request goes to the unprotected Internet. The Gateway was initially invented in part to help circumvent the shortage of Internet Protocol addresses on the Internet by isolating a private network from the Internet. The private network could then contain tens of thousands of Internet Protocol addresses also in use on the Internet, even if the Gateway only had a handful of addresses on the Internet side. When a request for an Internet connection came through the Gateway from the protected side, it would translate the internal address on the private network into a public Internet address on the unprotected side and send the request out, keep track of the transaction so that when it returned the Gateway would re-translate the address back to the private network address, and send the results back to the private network for routing. As a result of this function, the Gateway hid the structure and real addresses of the private network from the Internet. Thus, malicious parties on the unprotected Internet do not know the true nature of the structure of the protected local network. Further, if the Gateway receives a request to communicate with a processor it doesn't have a record of asking for such a communication, it stops the communications attempt (many firewalls also perform this function).
Other attempts at mitigating the hostile takeover of a processor, called a virus scanner, place specialized software on the processor that scans all Internet traffic going into it for patterns of behavior that are inappropriate or malicious code and stop them prior to being acted upon.
Most methods of mitigating hostile attempts to take over network connected processors have been so successful that only one method still remains, the ‘Buffer Overflow Attack’. See “Tools for Generating and Analyzing Attack Graphs” by Oleg Sheyner and Jeannette Wing, Carnegie Mellon University, Computer Science Department, 5000 Forbes Avenue, Pittsburgh, Pa. 15213, published in 2004, referencing page 357, FIG. 4 and the text between it and the start of section 4.2. Per the specified text in this paper, a properly configured and resourceful firewall will be sufficiently successful at stopping malicious internet intrusions that only a Buffer Overflow Attack (BOA) will succeed in taking control of processors protected by the firewall. This makes the BOA a prime source of attacks on firewall or gateway protected processors.
The BOA utilizes a weakness in the ‘C’ programming language (and several other computer languages). This weakness is that when a buffer in Main Memory 101a is set aside to temporarily hold incoming data (typically from the Internet), the programming language does not provide for a check to determine if the incoming data exceeds the buffer's size, overflowing it. An analogy would be to fill a glass with water on a restaurant table from a pitcher and not stop pouring water when the cup is full, spilling water all over the table as a result. Thus data written to the buffer could accidently, or maliciously in the event of a BOA, overflow past the boundary of the buffer and overwrite instructions in adjacent block of instructions in Main Memory 101a. If the data is actually malicious code intended to take control of the processor, and the Main Memory 101a adjacent to the buffer that is overflowing contains executable code, then the well behaved code will be overwritten by malicious code. The next time the code in the overflowed Main Memory 101a is executed, the processor becomes compromised.
Attempts to mitigate the BOA, such as logically separating blocks of Main Memory 101a so that locations where executable code reside is not always adjacent to incoming buffers, have been implemented. All of these attempts have reduced, but not eliminated BOAs. A different approach that provides a reliable means of stopping BOAs is needed.